// https://leetcode.cn/problems/wiggle-sort-ii/
// Created by ade on 2022/10/28.
// 给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
//
//你可以假设所有输入数组都可以得到满足题目要求的结果。
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // [1,1,2,1,2,2,1]
    //  1,1,1,1,2,2,2
    void wiggleSort(vector<int> &nums) {
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());
        int len = nums.size();
        int mid = len / 2;
        if (len % 2 == 0) {
            if (sorted[mid] == sorted[mid - 1]) {
                // 处理4,5,5,6 这种情况 6,5,5,4
                sort(sorted.begin(), sorted.begin() + mid, [](int &a, int &b) { return a > b; });
                sort(sorted.begin() + mid, sorted.end(), [](int &a, int &b) { return a > b; });
            }
            for (int i = 0; i < mid; i++) {
                nums[2 * i] = sorted[i];
                nums[2 * i + 1] = sorted[mid + i];
            }
        } else {
            nums[0] = sorted[0];
            for (int i = 0; i < mid; i++) {
                nums[2 * i + 1] = sorted[mid + i + 1];
                nums[2 * i + 2] = sorted[i + 1];
            }
        }
    }
};

int main() {
    Solution so;
//    vector<int> nums = {1,4,3,4,1,2,1,3,1,3,2,3,3};
    vector<int> nums = {4, 5, 5, 6};
    so.wiggleSort(nums);
    for (auto &i:nums) {
        cout << i << ",";
    }
    cout << endl;
    sort(nums.begin(), nums.end());
    return 0;
}